package sort;

import java.util.Arrays;

public class QuickSort {

    //找中间，归两边
    public static void main(String args[]) {

        int[] arr = new int[]{
                123, 12, 3, 123, 1, 23, 123, 1, 23, 12, 4, 5, 243, 52, 4, 52, 345, 243, 52, 43
        };

        quickSort(arr, 0, arr.length - 1);

        for (int i : arr)
            System.out.println(i);

    }

    static int findMiddleIndex(int arr[], int leftIndex, int rightIndex) {

        int middleValue = arr[leftIndex];

        while (leftIndex < rightIndex) {

            while (leftIndex < rightIndex && arr[rightIndex] >= middleValue) rightIndex--;
            arr[leftIndex] = arr[rightIndex];
            leftIndex++;

            while (leftIndex < rightIndex && arr[leftIndex] < middleValue) leftIndex++;
            arr[rightIndex] = arr[leftIndex];
            rightIndex--;
        }

        arr[leftIndex] = middleValue;
        return leftIndex;
    }

    static void quickSort(int arr[], int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex)
            return;

        int middleIndex = findMiddleIndex(arr, leftIndex, rightIndex);
        quickSort(arr, leftIndex, middleIndex - 1);
        quickSort(arr, middleIndex + 1, rightIndex);
    }


}
